{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Compatibility Score Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxCompatibilitySum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大兼容性评分和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一份由 <code>n</code> 个问题组成的调查问卷，每个问题的答案要么是 <code>0</code>（no，否），要么是 <code>1</code>（yes，是）。</p>\n",
    "\n",
    "<p>这份调查问卷被分发给 <code>m</code> 名学生和 <code>m</code> 名导师，学生和导师的编号都是从 <code>0</code> 到 <code>m - 1</code> 。学生的答案用一个二维整数数组 <code>students</code> 表示，其中 <code>students[i]</code> 是一个整数数组，包含第 <code>i</code> 名学生对调查问卷给出的答案（<strong>下标从 0 开始</strong>）。导师的答案用一个二维整数数组 <code>mentors</code> 表示，其中 <code>mentors[j]</code> 是一个整数数组，包含第 <code>j</code> 名导师对调查问卷给出的答案（<strong>下标从 0 开始</strong>）。</p>\n",
    "\n",
    "<p>每个学生都会被分配给 <strong>一名</strong> 导师，而每位导师也会分配到 <strong>一名</strong> 学生。配对的学生与导师之间的兼容性评分等于学生和导师答案相同的次数。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，学生答案为<code>[1, <strong><em>0</em></strong>, <strong><em>1</em></strong>]</code> 而导师答案为 <code>[0, <strong><em>0</em></strong>, <strong><em>1</em></strong>]</code> ，那么他们的兼容性评分为 2 ，因为只有第二个和第三个答案相同。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你找出最优的学生与导师的配对方案，以 <strong>最大程度上</strong> 提高 <strong>兼容性评分和</strong> 。</p>\n",
    "\n",
    "<p>给你 <code>students</code> 和 <code>mentors</code> ，返回可以得到的<em> </em><strong>最大兼容性评分和</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>按下述方式分配学生和导师：\n",
    "- 学生 0 分配给导师 2 ，兼容性评分为 3 。\n",
    "- 学生 1 分配给导师 0 ，兼容性评分为 2 。\n",
    "- 学生 2 分配给导师 1 ，兼容性评分为 3 。\n",
    "最大兼容性评分和为 3 + 2 + 3 = 8 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>任意学生与导师配对的兼容性评分都是 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == students.length == mentors.length</code></li>\n",
    "\t<li><code>n == students[i].length == mentors[j].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 8</code></li>\n",
    "\t<li><code>students[i][k]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "\t<li><code>mentors[j][k]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-compatibility-score-sum](https://leetcode.cn/problems/maximum-compatibility-score-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-compatibility-score-sum](https://leetcode.cn/problems/maximum-compatibility-score-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,0],[1,0,1],[0,0,1]]\\n[[1,0,0],[0,0,1],[1,1,0]]', '[[0,0],[0,0],[0,0]]\\n[[1,1],[1,1],[1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(students)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(idx, mask):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            \n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i): continue\n",
    "                score = sum(x == y for x, y in zip(students[idx], mentors[i]))\n",
    "                ans = max(ans, score + dp(idx+1, mask ^ (1 << i)))\n",
    "            return ans\n",
    "        \n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(students)\n",
    "\n",
    "        matrix = [[sum(a == b for a , b in zip (student, mentor)) for mentor in mentors]for student in students]\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for item in itertools.permutations(range(n)):\n",
    "            temp_sum = sum(matrix[i][item[i]] for i in range(n))\n",
    "            res = max(res, temp_sum)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        m = len(mentors)\n",
    "        n = len(mentors[0])\n",
    "        g = [[0] * m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    g[i][j] += int(students[i][k] == mentors[j][k])\n",
    "        \n",
    "        f = [0] * (1 << m)\n",
    "        for mask in range(1, 1 << m):\n",
    "            c = bin(mask).count(\"1\")\n",
    "            for i in range(m):\n",
    "                if mask & (1 << i):\n",
    "                    f[mask] = max(f[mask], f[mask ^ (1 << i)] + g[c - 1][i])\n",
    "        return f[(1 << m) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        m = len(students)\n",
    "        n = len(students[0])\n",
    "        \n",
    "        students = [int(''.join(str(ans) for ans in student), 2) for student in students]\n",
    "        mentors = [int(''.join(str(ans) for ans in mentor), 2) for mentor in mentors]\n",
    "        scores = [[n - (mentor^student).bit_count() for mentor in mentors] for student in students]\n",
    "\n",
    "        states = 1 << m\n",
    "        dp = [0 for _ in range(states)]\n",
    "\n",
    "        for state in range(states):\n",
    "            one_cnt = bin(state).count('1')\n",
    "            for i in range(m):\n",
    "                if (state >> i) & 1:\n",
    "                    dp[state] = max(dp[state], dp[state ^ (1 << i)] + scores[i][one_cnt - 1])\n",
    "        return dp[states - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students, mentors) -> int:\n",
    "        def helper(l1, l2):\n",
    "            ans = 0\n",
    "            for x, y in zip(l1, l2):\n",
    "                if x == y:\n",
    "                    ans +=1\n",
    "            return ans\n",
    "        def dfs(idx, cur_score):\n",
    "            nonlocal res\n",
    "            if idx == n:\n",
    "                res = max(res, cur_score)\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if check[i] == 1: continue\n",
    "                check[i] = 1\n",
    "                tmp = helper(students[idx], mentors[i])\n",
    "                dfs(idx+1, cur_score+tmp)\n",
    "                check[i] = 0\n",
    "\n",
    "        res, cur_score = 0, 0\n",
    "        n, m = len(students), len(students[0])\n",
    "        check = [0] * n\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        m, n = len(students), len(students[0])\n",
    "        g = [[0] * m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    g[i][j] += int(students[i][k] == mentors[j][k])\n",
    "        f = [0] * (1 << m)\n",
    "        for mask in range(1, 1 << m):\n",
    "            c = bin(mask).count(\"1\")\n",
    "            for i in range(m):\n",
    "                if mask & (1 << i):\n",
    "                    f[mask] = max(f[mask], f[mask ^ (1 << i)] + g[c-1][i])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        self.res = 0\n",
    "        self.students = students\n",
    "        self.go(0, mentors, 0)\n",
    "        return self.res\n",
    "\n",
    "    def go(self, k, mentors, s):\n",
    "        if not mentors:\n",
    "            self.res = max(self.res, s)\n",
    "            return\n",
    "        student = self.students[k]\n",
    "        for mentor in mentors:\n",
    "            g = len([True for i in range(len(mentor)) if mentor[i] == student[i]])\n",
    "            next_mentors = mentors.copy()\n",
    "            next_mentors.remove(mentor)\n",
    "            self.go(k+1, next_mentors, s + g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def cost(ls1,ls2):\n",
    "    r=0\n",
    "    for i in range(len(ls1)):\n",
    "        if ls1[i]==ls2[i]:\n",
    "            r+=1\n",
    "    return r\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n=len(students)\n",
    "        nums=[i for i in range(n)]\n",
    "        from itertools import permutations\n",
    "        perm = permutations(nums)\n",
    "        r=0\n",
    "        for lstrack in perm:\n",
    "            costsum=0\n",
    "            for i in range(n):\n",
    "                costsum+=cost(students[i],mentors[lstrack[i]])\n",
    "            r=max(costsum,r)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        m = len(students)\n",
    "        n = len(students[0])\n",
    "        compatibility = [[0] * m for i in range(m)];\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    compatibility[i][j] += students[i][k] == mentors[j][k];\n",
    "        \n",
    "        f = [0] * (1 << m);\n",
    "        for mask in range(1 << m):\n",
    "            c = bin(mask).count(\"1\")\n",
    "            for i in range(m):\n",
    "                if mask >> i & 1:\n",
    "                    f[mask] = max(f[mask], f[mask ^ (1 << i)] + compatibility[c - 1][i])\n",
    "        return f[(1 << m) - 1];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        def cal(i,j):\n",
    "            s = students[i]\n",
    "            m = mentors[j]\n",
    "            res = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == m[i]:\n",
    "                    res += 1\n",
    "            return res\n",
    "        n = len(mentors)\n",
    "        vis = [0 for i in range(n)]\n",
    "        ans = 0\n",
    "        def dfs(index,vis,score):\n",
    "            if index == n:\n",
    "                nonlocal ans\n",
    "                ans = max(ans,score)\n",
    "                return\n",
    "            else:\n",
    "                for j in range(n):\n",
    "                    if vis[j] == 0:\n",
    "                        vis[j] = 1\n",
    "                        tmp = cal(index,j)\n",
    "                        score += tmp\n",
    "                        dfs(index+1,vis,score)\n",
    "                        vis[j] = 0\n",
    "                        score -= tmp\n",
    "        dfs(0,vis,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        k = len(students[0])\n",
    "        ans = 0\n",
    "        for one in permutations(mentors):\n",
    "            cnt = 0\n",
    "            for x,y in zip(students,one):\n",
    "                for i in range(k):\n",
    "                    cnt += int(x[i] == y[i])\n",
    "            ans = max(cnt,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        f = lambda a: [sum(1 << i for i, c in enumerate(x) if c) for x in a]\n",
    "        m, n = len(mentors), len(mentors[0])\n",
    "        students, mentors = f(students), f(mentors)\n",
    "        a = [inf] * (1 << m)\n",
    "        a[0] = 0\n",
    "        for i in range(1, len(a)):\n",
    "            c = students[i.bit_count() - 1]\n",
    "            for j in range(i.bit_length()):\n",
    "                k = 1 << j\n",
    "                if i & k:\n",
    "                    a[i] = min(a[i], a[i ^ k] + (c ^ mentors[j]).bit_count())\n",
    "        return m * n - a.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        # 预处理 每个学生和导师的兼容性评分\n",
    "        m = len(students)\n",
    "        n = len(students[0])\n",
    "        g = [[0]*m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    g[i][j] += int(students[i][k]==mentors[j][k])\n",
    "\n",
    "        # 枚举所有的排列组合\n",
    "        ans = 0\n",
    "        p = list(range(m))\n",
    "        for f in permutations(p):\n",
    "            cnt = sum(g[i][f[i]] for i in range(m))\n",
    "            ans = max(ans,cnt)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        f = lambda a: (sum(1 << i for i, c in enumerate(x) if c) for x in a)\n",
    "        a, b = Counter(f(students)), list(f(mentors))\n",
    "        m = inf\n",
    "        \n",
    "        def f(s):\n",
    "            nonlocal m\n",
    "            if not b:\n",
    "                m = min(m, s)\n",
    "                return\n",
    "            x = b.pop()\n",
    "            for i in tuple(a):\n",
    "                if a[i] == 1:\n",
    "                    del a[i]\n",
    "                else:\n",
    "                    a[i] -= 1\n",
    "                f(s + (x ^ i).bit_count())\n",
    "                a[i] += 1\n",
    "            b.append(x)\n",
    "            \n",
    "        f(0)\n",
    "        return len(mentors) * len(mentors[0]) - m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        m = len(students[0])\n",
    "        def dfs(cnt, i):\n",
    "            nonlocal ans\n",
    "            if cnt + (n - i) * m <= ans:\n",
    "                return\n",
    "            if i == n:\n",
    "                if cnt > ans: ans = cnt\n",
    "                return \n",
    "            for j, x in enumerate(students):\n",
    "                if not vis[j]:\n",
    "                    vis[j] = True\n",
    "                    score = sum(int(x==y) for x, y in zip(students[j], mentors[i]))\n",
    "                    dfs(cnt + score, i + 1)\n",
    "                    vis[j] = False\n",
    "        n = len(students)\n",
    "        ans = 0\n",
    "        vis = [False] * n\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(mentors)\n",
    "        f = [0] * (1 << n)\n",
    "        for i in range(1 << n):\n",
    "            cnt = i.bit_count()\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    f[i] = max(f[i], f[i ^ (1 << j)] + sum(a == b for a, b in zip(students[cnt - 1], mentors[j])))\n",
    "        return f[(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(mentors)\n",
    "        m = len(students[0])\n",
    "        def process(arr):\n",
    "            cur = 0\n",
    "            for now in arr:\n",
    "                cur <<= 1\n",
    "                cur |= now\n",
    "            return cur\n",
    "        students = [process(i) for i in students]\n",
    "        mentors = [process(i) for i in mentors]\n",
    "        @cache\n",
    "        def dfs(index, cur_state):\n",
    "            if index == n:\n",
    "                return 0\n",
    "            cur = 0\n",
    "            for j in range(n):\n",
    "                if (cur_state >> j) & 1 == 0:\n",
    "                    cur = max(cur, m - (students[index] ^ mentors[j]).bit_count() + dfs(index + 1, cur_state | (1 << j)))\n",
    "            return cur\n",
    "        ans = dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        m, n = len(students), len(students[0])\n",
    "        g = [[0] * m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    g[i][j] += int(students[i][k] == mentors[j][k])\n",
    "\n",
    "        f = [0] * (1 << m)\n",
    "        for mask in range(1, 1 << m):\n",
    "            c = bin(mask).count(\"1\")\n",
    "            for i in range(m):\n",
    "                # 判断 mask 的第 i 位是否为 1\n",
    "                if mask & (1 << i):\n",
    "                    f[mask] = max(f[mask], f[mask ^ (1 << i)] + g[c - 1][i])\n",
    "        \n",
    "        return f[(1 << m) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        \n",
    "        # enum method\n",
    "        m, n = len(students), len(students[0])\n",
    "        scores = [[0] * m for _ in range(m)]\n",
    "\n",
    "        for stud_idx, student in enumerate(students):\n",
    "            for ment_idx, mentor in enumerate(mentors):\n",
    "                for stud, ment in zip(student, mentor):\n",
    "                    scores[stud_idx][ment_idx] += int(stud == ment)\n",
    "        \n",
    "        ret_score = 0\n",
    "        for p_ment_idx in permutations(range(m)):\n",
    "            p_score = 0\n",
    "            for stud_idx, ment_idx in zip(range(m), p_ment_idx):\n",
    "                p_score += scores[stud_idx][ment_idx]\n",
    "            ret_score = max(ret_score, p_score)\n",
    "        \n",
    "        return ret_score\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        m = len(students)\n",
    "        n = len(students[0])\n",
    "\n",
    "        score = [[0 for _ in range(m)] for _ in range(m)]\n",
    "        for i, stu in enumerate(students):\n",
    "            for j, men in enumerate(mentors):\n",
    "                cur = 0\n",
    "                for st, me in zip(stu, men):\n",
    "                    cur += (st == me)\n",
    "                score[i][j] = cur\n",
    "        \n",
    "        used = [False for _ in range(m)]\n",
    "        cur = 0\n",
    "        max_ = 0\n",
    "\n",
    "        def backtrace(si: int) -> None:\n",
    "            nonlocal cur, max_\n",
    "            if si == m:\n",
    "                max_ = max(max_, cur)\n",
    "                return\n",
    "            for j in range(m):\n",
    "                if used[j] == False:\n",
    "                    cur += score[si][j]\n",
    "                    used[j] = True\n",
    "                    backtrace(si + 1)\n",
    "                    used[j] = False\n",
    "                    cur -= score[si][j]\n",
    "        backtrace(0)\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for students2 in permutations(students):\n",
    "            t = 0\n",
    "            for a, b in zip(students2, mentors):\n",
    "                t += sum(x == y for x, y in zip(a, b))\n",
    "            ans = max(ans, t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        \n",
    "        def check(i, j):\n",
    "            return sum(a == b for a, b in zip(students[i], mentors[j]))\n",
    "\n",
    "        seen = set()\n",
    "        self.ans = 0\n",
    "        def dfs(i, score):\n",
    "            if i == len(students):\n",
    "                self.ans = max(self.ans, score)\n",
    "\n",
    "            \n",
    "            for j in range(len(mentors)):\n",
    "                if j not in seen:\n",
    "                    seen.add(j)\n",
    "                    dfs(i + 1, score + check(i, j))\n",
    "                    seen.remove(j)\n",
    "        \n",
    "        dfs(0, 0)\n",
    "\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(mentors)\n",
    "        g = [[sum(x == y for x, y in zip(s, m)) for m in mentors] for s in students]\n",
    "        f = [0] * (1 << n)\n",
    "        for mask in range(1, 1 << n):\n",
    "            c = bin(mask).count(\"1\")\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1:\n",
    "                    f[mask] = max(f[mask], f[mask ^ (1 << i)] + g[c - 1][i])\n",
    "        return f[(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        \n",
    "        m, n = len(students), len(students[0])\n",
    "        scores = [[0] * m for _ in range(m)]\n",
    "\n",
    "        for stud_idx, student in enumerate(students):\n",
    "            for ment_idx, mentor in enumerate(mentors):\n",
    "                for stud, ment in zip(student, mentor):\n",
    "                    scores[stud_idx][ment_idx] += int(stud == ment)\n",
    "        \n",
    "        # enum method\n",
    "        # ret_score = 0\n",
    "        # for p_ment_idx in permutations(range(m)):\n",
    "        #     p_score = 0\n",
    "        #     for stud_idx, ment_idx in zip(range(m), p_ment_idx):\n",
    "        #         p_score += scores[stud_idx][ment_idx]\n",
    "        #     ret_score = max(ret_score, p_score)\n",
    "        # return ret_score\n",
    "\n",
    "        f = [0] * (1 << m)\n",
    "        for mask in range(1, 1<<m):\n",
    "            cnt_assign = bin(mask).count('1')\n",
    "            for i in range(m):\n",
    "                if mask & (1 << i):\n",
    "                    f[mask] = max(f[mask], f[mask ^ (1 << i)] + scores[cnt_assign - 1][i])\n",
    "        return f[(1 << m) -1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(students)\n",
    "        match = [[0] * n for _ in range(n)]\n",
    "        for i, arr1 in enumerate(students):\n",
    "            for j, arr2 in enumerate(mentors):\n",
    "                match[i][j] = sum(a == b for a, b in zip(arr1, arr2))\n",
    "        \n",
    "        ans = 0\n",
    "        for perm in permutations(range(n)):\n",
    "            ans = max(ans, sum(match[i][j] for i, j in zip(range(n), perm)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        m = len(students[0])\n",
    "        def dfs(cnt, i):\n",
    "            nonlocal ans\n",
    "            if cnt + (n - i) * m <= ans:\n",
    "                return\n",
    "            if i == n:\n",
    "                ans = max(ans, cnt)\n",
    "                return \n",
    "            for j, x in enumerate(students):\n",
    "                if not vis[j]:\n",
    "                    vis[j] = True\n",
    "                    score = sum(int(x==y) for x, y in zip(students[j], mentors[i]))\n",
    "                    dfs(cnt + score, i + 1)\n",
    "                    vis[j] = False\n",
    "        n = len(students)\n",
    "        ans = 0\n",
    "        vis = [False] * n\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for students2 in permutations(students):\n",
    "            t = 0\n",
    "            for a, b in zip(students2, mentors):\n",
    "                for x, y in zip(a, b):\n",
    "                    t += x == y\n",
    "            ans = max(ans, t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "      self.res = 0\n",
    "\n",
    "    def caculate(self, students, mentors):\n",
    "      res = 0\n",
    "      for x in zip(students, mentors):\n",
    "        if len(set(x)) == 1:\n",
    "          res += 1\n",
    "      return res\n",
    "\n",
    "    def dfs(self, students, mentors, visited, stu_index, cur_sum):\n",
    "      if stu_index == len(students):\n",
    "        self.res = max(self.res, cur_sum)\n",
    "        return \n",
    "\n",
    "      for men_index in range(len(mentors)):\n",
    "        if men_index not in visited:\n",
    "          tmp_sum = self.caculate(students[stu_index], mentors[men_index])\n",
    "          visited.add(men_index)\n",
    "          self.dfs(students, mentors, visited,  stu_index + 1, cur_sum + tmp_sum)\n",
    "          visited.remove(men_index)\n",
    "\n",
    "\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "      cur_sum = 0\n",
    "      visited = set()\n",
    "      self.dfs(students, mentors, visited, 0, cur_sum)\n",
    "      return self.res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(students)\n",
    "        m = len(students[0])\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(m):\n",
    "                    g[i][j] += int(students[i][k] == mentors[j][k])\n",
    "        def dfs(cnt, i):\n",
    "            nonlocal ans\n",
    "            if cnt + (n - i) * m <= ans:\n",
    "                return\n",
    "            if i == n:\n",
    "                if cnt > ans: ans = cnt\n",
    "                return \n",
    "            for j, x in enumerate(students):\n",
    "                if not vis[j]:\n",
    "                    vis[j] = True\n",
    "                    dfs(cnt + g[j][i], i + 1)\n",
    "                    vis[j] = False\n",
    "        ans = 0\n",
    "        vis = [False] * n\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "\n",
    "        return max(sum(sum(x == y for x,y in zip(a,b)) for a,b in zip(st, mentors)) for st in permutations(students) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        def calc(arr):\n",
    "            num = 0\n",
    "            for x in arr:\n",
    "               num |= x\n",
    "               num <<= 1\n",
    "            return num\n",
    "        l = len(students[0])\n",
    "        nums1 = [calc(arr) for arr in students]\n",
    "        nums2 = [calc(arr) for arr in mentors]\n",
    "        n = len(nums1)\n",
    "        m = 1 << n\n",
    "        bitcnt = [0] * m\n",
    "        for i in range(n):\n",
    "            bit = 1 << i\n",
    "            for j in range(bit):\n",
    "                bitcnt[bit | j] = bitcnt[j] + 1\n",
    "        masks = [[] for _ in range(n+1)]\n",
    "        for mask, cnt in enumerate(bitcnt):\n",
    "            masks[cnt].append(mask)\n",
    "\n",
    "        dp = [0] * m\n",
    "        for i, x in enumerate(nums1):\n",
    "            for mask in reversed(masks[i+1]):\n",
    "                for j, y in enumerate(nums2):\n",
    "                    if mask >> j & 1:\n",
    "                        dp[mask] = max(dp[mask], dp[mask ^ (1 << j)] + l - (x ^ y).bit_count())\n",
    "\n",
    "        return dp[m-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def caculate(self, students, mentors):\n",
    "      res = 0\n",
    "      for i in range(len(students)):\n",
    "        for j in range(len(students[0])):\n",
    "          if students[i][j] == mentors[i][j]:\n",
    "            res += 1\n",
    "        \n",
    "      return res\n",
    "\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "      res = -inf\n",
    "      for student in permutations(students):\n",
    "        res = max(res, self.caculate(student, mentors))\n",
    "      return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        store=dict()\n",
    "\n",
    "        def dp(stu,men,store):\n",
    "            if len(stu)==1:\n",
    "                res=0\n",
    "                if (tuple(stu[0]),tuple(men[0])) in store:\n",
    "                    res+=store[(tuple(stu[0]),tuple(men[0]))]\n",
    "                    return res\n",
    "                else:\n",
    "                    for i in range (len(stu[0])):\n",
    "                        res+=1-abs(stu[0][i]-men[0][i])\n",
    "                    store[(tuple(stu[0]),tuple(men[0]))]=res\n",
    "                    return res\n",
    "            else:\n",
    "                maxx=0\n",
    "                curstu=stu[0]\n",
    "                for ind in range (len(men)):\n",
    "                    curmen=men[ind]\n",
    "                    if (tuple(curstu),tuple(curmen)) in store:\n",
    "                        curres=store[(tuple(curstu),tuple(curmen))]+dp(stu[1:],men[0:ind]+men[ind+1:],store)\n",
    "                    else:\n",
    "                        curres=0\n",
    "                        for i in range (len(curstu)):\n",
    "                            curres+=1-abs(curstu[i]-curmen[i])\n",
    "                        store [(tuple(curstu),tuple(curmen))]=curres\n",
    "                        curres+=dp(stu[1:],men[0:ind]+men[ind+1:],store)\n",
    "                    if curres>maxx:\n",
    "                        maxx=curres\n",
    "                return maxx\n",
    "        return dp(students,mentors,store)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(students)\n",
    "        m = len(students[0])\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(m):\n",
    "                    g[i][j] += int(students[i][k] == mentors[j][k])\n",
    "        f = [0] * (1 << n)\n",
    "        for mask in range(1 << n):\n",
    "            ind = mask.bit_count()\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    f[mask] = max(f[mask], f[mask ^ (1<<i)] + g[ind - 1][i])\n",
    "        return f[-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\r\n",
    "        def getScore(a, b):\r\n",
    "            return sum([1 if x == y else 0 for x, y in zip(a, b)])\r\n",
    "        n = len(students)\r\n",
    "        dp = [[0] * (1 << n) for _ in range(n)]\r\n",
    "        for i in range(n):\r\n",
    "            for j in range(1 << n):\r\n",
    "                if bin(j).count('1') == i + 1:\r\n",
    "                    for k in range(n):\r\n",
    "                        if j & (1 << k):\r\n",
    "                            dp[i][j] = max(dp[i][j], dp[i-1][j ^ (1 << k)] + getScore(students[i], mentors[k]))\r\n",
    "        return dp[n-1][(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        def nextPermutation(arr):\n",
    "            # 求一个排列的下一个排列\n",
    "            # 包括有相同数也可以求\n",
    "            i = len(arr)-2\n",
    "            while i >= 0 and arr[i] >= arr[i+1]:\n",
    "                i -= 1\n",
    "            if i < 0:\n",
    "                return False\n",
    "            else:\n",
    "                # 交换\n",
    "                j = len(arr)-1\n",
    "                while j >= 0 and arr[i] >= arr[j]:\n",
    "                    j -= 1\n",
    "                arr[i],arr[j] = arr[j],arr[i]\n",
    "            # 对arr排序\n",
    "            left = i+1\n",
    "            right = len(arr)-1\n",
    "            while left < right:\n",
    "                arr[left],arr[right] = arr[right],arr[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return True\n",
    "        # 预处理每位老师和学生的兼容性\n",
    "        m = len(students)\n",
    "        n = len(students[0])\n",
    "        g = [[0]*m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    g[i][j] += int(students[i][k]==mentors[j][k])\n",
    "        # 枚举所有的全排列\n",
    "        ans = 0\n",
    "        arr = list(range(m))\n",
    "        while True:\n",
    "            cur = sum(g[i][arr[i]] for i in range(m))\n",
    "            ans = max(ans,cur)\n",
    "            # 时间复杂度(O(m))\n",
    "            if not nextPermutation(arr):\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(mentors)\n",
    "        f = [0] * (1 << n)\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                g[i][j] = sum(a == b for a, b in zip(students[i], mentors[j]))\n",
    "        for i in range(1 << n):\n",
    "            cnt = i.bit_count()\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    f[i] = max(f[i], f[i ^ (1 << j)] + g[cnt-1][j])\n",
    "        return f[(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        def pipei(l1,l2):\n",
    "            return sum([1 if x == y else 0 for x,y in zip(l1,l2)])\n",
    "        n = len(students)\n",
    "        a = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                a[i][j] = pipei(students[i],mentors[j])\n",
    "        perms = permutations(range(n))\n",
    "        ans = 0\n",
    "        for perm in perms:\n",
    "            ans = max(ans,sum([a[i][perm[i]] for i in range(n)]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        def cal(i,j):\n",
    "            s = students[i]\n",
    "            m = mentors[j]\n",
    "            res = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == m[i]:\n",
    "                    res += 1\n",
    "            return res\n",
    "        n = len(mentors)\n",
    "        vis = [0 for i in range(n)]\n",
    "        ans = 0\n",
    "        def dfs(index,vis,score):\n",
    "            if index == n:\n",
    "                nonlocal ans\n",
    "                ans = max(ans,score)\n",
    "                return\n",
    "            else:\n",
    "                for j in range(n):\n",
    "                    if vis[j] == 0:\n",
    "                        vis[j] = 1\n",
    "                        tmp = cal(index,j)\n",
    "                        dfs(index+1,vis,score+tmp)\n",
    "                        vis[j] = 0\n",
    "        dfs(0,vis,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        def cal(i,j):\n",
    "            s = students[i]\n",
    "            m = mentors[j]\n",
    "            res = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == m[i]:\n",
    "                    res += 1\n",
    "            return res\n",
    "        n = len(mentors)\n",
    "        vis = [0 for i in range(n)]\n",
    "        ans = 0\n",
    "        def dfs(index,vis,score):\n",
    "            if index == n:\n",
    "                nonlocal ans\n",
    "                ans = max(ans,score)\n",
    "            else:\n",
    "                for j in range(n):\n",
    "                    if vis[j] == 0:\n",
    "                        vis[j] = 1\n",
    "                        tmp = cal(index,j)\n",
    "                        dfs(index+1,vis,score+tmp)\n",
    "                        vis[j] = 0\n",
    "        dfs(0,vis,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Helper:\n",
    "    @staticmethod\n",
    "    def nextPermutation(nums: List[int]) -> bool:\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return False\n",
    "\n",
    "        if i >= 0:\n",
    "            j = len(nums) - 1\n",
    "            while j >= 0 and nums[i] >= nums[j]:\n",
    "                j -= 1\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "        \n",
    "        left, right = i + 1, len(nums) - 1\n",
    "        while left < right:\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        \n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        m, n = len(students), len(students[0])\n",
    "        g = [[0] * m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    g[i][j] += int(students[i][k] == mentors[j][k])\n",
    "\n",
    "        p = list(range(m))\n",
    "        ans = 0\n",
    "\n",
    "        while True:\n",
    "            cur = sum(g[i][p[i]] for i in range(m))\n",
    "            ans = max(ans, cur)\n",
    "            if not Helper.nextPermutation(p):\n",
    "                break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(mentors)\n",
    "        m = len(students[0])\n",
    "        def process(arr):\n",
    "            cur = 0\n",
    "            for now in arr:\n",
    "                cur <<= 1\n",
    "                cur |= now\n",
    "            return cur\n",
    "        students = [process(i) for i in students]\n",
    "        mentors = [process(i) for i in mentors]\n",
    "        \n",
    "        def dfs(index, has):\n",
    "            if index == n:\n",
    "                return 0 \n",
    "            cur = 0\n",
    "            tmp = has.copy()\n",
    "            for other in tmp:\n",
    "                has.remove(other)\n",
    "                cur = max(cur, m - (students[index] ^ mentors[other]).bit_count() + dfs(index + 1, has))\n",
    "                has.add(other)\n",
    "            return cur\n",
    "        return dfs(0, set(range(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cal_match(self, students, mentors, n, m):\n",
    "        res = [[0] * m for _ in range(m)]\n",
    "        for student_i, student in enumerate(students):\n",
    "            for mentor_i, mentor in enumerate(mentors):\n",
    "                for i in range(n):\n",
    "                    if student[i] == mentor[i]:\n",
    "                        res[student_i][mentor_i] += 1\n",
    "        return res\n",
    "    \n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        m = len(students)\n",
    "        n = len(students[0])\n",
    "        match_cost = self.cal_match(students, mentors, n, m)\n",
    "        dp = [0] * (1 << m)\n",
    "\n",
    "        for i in range(1, 1 << m):\n",
    "            cnt = 0\n",
    "            for j in range(m):\n",
    "                cnt += (i >> j) & 1\n",
    "            \n",
    "            for j in range(m):\n",
    "                if (i >> j) & 1:\n",
    "                    dp[i] = max(dp[i], dp[i - (1 << j)] + match_cost[cnt - 1][j])\n",
    "        return dp[(1 << m) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(students)\n",
    "        match = [[0] * n for _ in range(n)]\n",
    "        for i, arr1 in enumerate(students):\n",
    "            for j, arr2 in enumerate(mentors):\n",
    "                match[i][j] = sum(a == b for a, b in zip(arr1, arr2))\n",
    "        \n",
    "        m = 1 << n\n",
    "        bitcnt = [0] * m\n",
    "        for i in range(n):\n",
    "            bit = 1 << i\n",
    "            for j in range(bit):\n",
    "                bitcnt[bit | j] = bitcnt[j] + 1\n",
    "        masks = [[] for _ in range(n+1)]\n",
    "        for mask, cnt in enumerate(bitcnt):\n",
    "            masks[cnt].append(mask)\n",
    "\n",
    "        dp = [0] * m\n",
    "        for i in range(n):\n",
    "            for mask in reversed(masks[i+1]):\n",
    "                for j in range(n):\n",
    "                    if mask >> j & 1:\n",
    "                        dp[mask] = max(dp[mask], dp[mask ^ (1 << j)] + match[i][j])\n",
    "\n",
    "        return dp[m-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        \n",
    "        m = len(students)\n",
    "        n = len(students[0])\n",
    "        scores = [[0]*m for _ in range(m)]      # scores[i][j] 学生i与导师j之间的兼容性评分\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    scores[i][j] += int(students[i][k] == mentors[j][k])\n",
    "\n",
    "\n",
    "        # 按照编号顺序给每一名学生分配老师        \n",
    "        @lru_cache(None)\n",
    "        def dfs(mask):\n",
    "            i = bin(mask).count('1')    # 有i个学生(0到i-1)已经分配了导师\n",
    "\n",
    "            if i==m:                    # 全部分配完毕\n",
    "                return 0\n",
    "            \n",
    "            ans = 0\n",
    "            for j in range(m):              # 尝试为学生i（即第i+1个学生）分配导师j\n",
    "                if mask & (1<<j) == 0:      # 若导师j未被分配学生，则为其分配学生i，则状态标志变为 mask+(1<<j)\n",
    "                    ans = max(ans, dfs(mask+(1<<j)) + scores[i][j])\n",
    "            \n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        def get(a):\n",
    "            ans = []\n",
    "            for st in a:\n",
    "                t = 0\n",
    "                for i, x in enumerate(st):\n",
    "                    if x == 1:\n",
    "                        t |= 1 << i\n",
    "                ans.append(t)\n",
    "            return ans\n",
    "        a1 = get(students)\n",
    "        # print(f'{a1}')\n",
    "        a2 = get(mentors)\n",
    "        n = len(students[0])\n",
    "        ans = 0\n",
    "        for p in permutations(a1):\n",
    "            # print(f'{p},{a2}')\n",
    "            cnt = sum(n - (x^y).bit_count() for x, y in zip(p, a2))\n",
    "            ans = max(ans, cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == n:\n",
    "             return 0\n",
    "          c = j ^ u\n",
    "          res = 0\n",
    "          while c:\n",
    "             index = (c & -c).bit_length() - 1\n",
    "             res = max(res, dfs(i + 1, j | (1 << index)) + (stu_mask[i] ^ men_mask[index] ^ m).bit_count())\n",
    "             c &= c - 1\n",
    "          return res\n",
    "       n = len(students)\n",
    "       stu_mask = [0] * n\n",
    "       men_mask = [0] * n\n",
    "       for i in range(n):\n",
    "          cur = 0\n",
    "          for v in students[i]:\n",
    "             cur = (cur << 1) | v\n",
    "          stu_mask[i] = cur\n",
    "          cur = 0\n",
    "          for v in mentors[i]:\n",
    "             cur = (cur << 1) | v\n",
    "          men_mask[i] = cur\n",
    "       m = (1 << len(students[0])) - 1\n",
    "       u = (1 << n) - 1\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "from typing import List, Tuple\n",
    "from collections import deque\n",
    "INF = int(1e18)\n",
    "class Edge:\n",
    "    __slots__ = (\"fromV\", \"toV\", \"cap\", \"cost\", \"flow\")\n",
    "    def __init__(self, fromV: int, toV: int, cap: int, cost: int, flow: int) -> None:\n",
    "        self.fromV = fromV\n",
    "        self.toV = toV\n",
    "        self.cap = cap\n",
    "        self.cost = cost\n",
    "        self.flow = flow\n",
    "class MinCostMaxFlowEK:\n",
    "    \"\"\"最小费用流的复杂度为流量*spfa的复杂度\"\"\"\n",
    "    __slots__ = (\"_n\", \"_start\", \"_end\", \"_edges\", \"_reGraph\", \"_dist\", \"_pre\", \"_flow\")\n",
    "    def __init__(self, n: int, start: int, end: int):\n",
    "        \"\"\"\n",
    "        Args:\n",
    "            n (int): 包含虚拟点在内的总点数\n",
    "            start (int): (虚拟)源点\n",
    "            end (int): (虚拟)汇点\n",
    "        \"\"\"\n",
    "        assert 0 <= start < n and 0 <= end < n\n",
    "        self._n = n\n",
    "        self._start = start\n",
    "        self._end = end\n",
    "        self._edges: List[\"Edge\"] = []\n",
    "        self._reGraph: List[List[int]] = [[] for _ in range(n)]  # 残量图存储的是边的下标\n",
    "\n",
    "        self._dist = [INF] * n\n",
    "        self._flow = [0] * n\n",
    "        self._pre = [-1] * n\n",
    "    def addEdge(self, fromV: int, toV: int, cap: int, cost: int) -> None:\n",
    "        \"\"\"原边索引为i 反向边索引为i^1\"\"\"\n",
    "        self._edges.append(Edge(fromV, toV, cap, cost, 0))\n",
    "        self._edges.append(Edge(toV, fromV, 0, -cost, 0))\n",
    "        len_ = len(self._edges)\n",
    "        self._reGraph[fromV].append(len_ - 2)\n",
    "        self._reGraph[toV].append(len_ - 1)\n",
    "    def work(self) -> Tuple[int, int]:\n",
    "        \"\"\"\n",
    "        Returns:\n",
    "            Tuple[int, int]: [最大流,最小费用]\n",
    "        \"\"\"\n",
    "        maxFlow, minCost = 0, 0\n",
    "        while self._spfa():\n",
    "            delta = self._flow[self._end]\n",
    "            minCost += delta * self._dist[self._end]\n",
    "            maxFlow += delta\n",
    "            cur = self._end\n",
    "            while cur != self._start:\n",
    "                edgeIndex = self._pre[cur]\n",
    "                self._edges[edgeIndex].flow += delta\n",
    "                self._edges[edgeIndex ^ 1].flow -= delta\n",
    "                cur = self._edges[edgeIndex].fromV\n",
    "        return maxFlow, minCost\n",
    "    def _spfa(self) -> bool:\n",
    "        \"\"\"spfa沿着最短路寻找增广路径  有负cost的边不能用dijkstra\"\"\"\n",
    "        n, start, end, edges, reGraph = (\n",
    "            self._n,\n",
    "            self._start,\n",
    "            self._end,\n",
    "            self._edges,\n",
    "            self._reGraph,\n",
    "        )\n",
    "        self._flow = flow = [0] * n\n",
    "        self._pre = pre = [-1] * n\n",
    "        self._dist = dist = [INF] * n\n",
    "        dist[start] = 0\n",
    "        flow[start] = INF\n",
    "        inQueue = [False] * n\n",
    "        inQueue[start] = True\n",
    "        queue = deque([start])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            inQueue[cur] = False\n",
    "            for edgeIndex in reGraph[cur]:\n",
    "                edge = edges[edgeIndex]\n",
    "                cost, remain, next = edge.cost, edge.cap - edge.flow, edge.toV\n",
    "                if remain > 0 and dist[cur] + cost < dist[next]:\n",
    "                    dist[next] = dist[cur] + cost\n",
    "                    pre[next] = edgeIndex\n",
    "                    flow[next] = remain if remain < flow[cur] else flow[cur]\n",
    "                    if not inQueue[next]:\n",
    "                        inQueue[next] = True\n",
    "                        if queue and dist[queue[0]] > dist[next]:\n",
    "                            queue.appendleft(next)\n",
    "                        else:\n",
    "                            queue.append(next)\n",
    "        return pre[end] != -1\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n=len(students)\n",
    "        st=2*n+5\n",
    "        ed=2*n+1\n",
    "        mc=MinCostMaxFlowEK(2*n+10,st,ed)\n",
    "        for i in range(n):\n",
    "            mc.addEdge(st,i,1,0)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                cost=sum(x==y for x,y in zip(students[i],mentors[j]))\n",
    "                mc.addEdge(i,j+n,1,-cost)\n",
    "        for j in range(n):\n",
    "            mc.addEdge(j+n,ed,1,0)\n",
    "        return -mc.work()[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        def get(a):\n",
    "            ans = []\n",
    "            for st in a:\n",
    "                t = 0\n",
    "                for i, x in enumerate(st):\n",
    "                    if x == 1:\n",
    "                        t |= 1 << i\n",
    "                ans.append(t)\n",
    "            return ans\n",
    "        a1 = get(students)\n",
    "        a2 = get(mentors)\n",
    "        m = len(students[0])\n",
    "        def dfs(cnt, i):\n",
    "            nonlocal ans\n",
    "            if cnt + (n - i) * m <= ans:\n",
    "                return\n",
    "            if i == n:\n",
    "                ans = max(ans, cnt)\n",
    "                return \n",
    "            for j, x in enumerate(a1):\n",
    "                if not vis[j]:\n",
    "                    vis[j] = True\n",
    "                    score = m - (x^a2[i]).bit_count()\n",
    "                    dfs(cnt + score, i + 1)\n",
    "                    vis[j] = False\n",
    "        n = len(students)\n",
    "        ans = 0\n",
    "        vis = [False] * n\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        #状压DP\n",
    "        #dp[m]表示状态为m的最大兼容性评分和\n",
    "        m,n=len(students),len(students[0])\n",
    "        k=1<<m\n",
    "        dp=[0]*k\n",
    "        #需要预处理兼容性查询表\n",
    "        check=[[0]*m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                for r in range(n):\n",
    "                    check[i][j]+=(students[i][r]==mentors[j][r])\n",
    "        #通过枚举第cnt-1个学生可与哪个老师匹配进行状态转移\n",
    "        for i in range(1,k):\n",
    "            cnt=bin(i).count(\"1\")\n",
    "            for j in range(m):\n",
    "                if i>>j&1:\n",
    "                    dp[i]=max(dp[i],dp[i^(1<<j)]+check[cnt-1][j])\n",
    "        return dp[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(students)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, mask):\n",
    "            res = 0\n",
    "            for j in range(n):\n",
    "                if mask & (1 << j): continue\n",
    "                res = max(res, dfs(i+1, mask | (1 << j)) + sum(x==y for x, y in zip(students[i], mentors[j])))\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, 0)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        def get(a):\n",
    "            ans = []\n",
    "            for st in a:\n",
    "                t = 0\n",
    "                for i, x in enumerate(st):\n",
    "                    if x == 1:\n",
    "                        t |= 1 << i\n",
    "                ans.append(t)\n",
    "            return ans\n",
    "        a1 = get(students)\n",
    "        a2 = get(mentors)\n",
    "        def dfs(cnt, i):\n",
    "            nonlocal ans\n",
    "            if i == n:\n",
    "                ans = max(ans, cnt)\n",
    "                return \n",
    "            for j, x in enumerate(a1):\n",
    "                if not vis[j]:\n",
    "                    vis[j] = True\n",
    "                    score = len(students[0]) - (x^a2[i]).bit_count()\n",
    "                    dfs(cnt + score, i + 1)\n",
    "                    vis[j] = False\n",
    "        n = len(students)\n",
    "        ans = 0\n",
    "        vis = [False] * n\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        m=len(students)\n",
    "        n=len(students[0])\n",
    "        dis=[[0]*m for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                tmp=0\n",
    "                a=students[i]\n",
    "                b=mentors[j]\n",
    "                for k in range(n):\n",
    "                    if a[k]==b[k]:\n",
    "                        tmp+=1\n",
    "                dis[i][j]=tmp \n",
    "      #  print(dis)\n",
    "        vis=[0]*m \n",
    "        ans=-float(\"inf\")\n",
    "        def dfs(i,t):\n",
    "            nonlocal ans \n",
    "            if i==m:\n",
    "                ans=max(ans,t)\n",
    "                return \n",
    "            for j in range(m):\n",
    "                if vis[j]==0:\n",
    "                    vis[j]=1\n",
    "                    dfs(i+1,t+dis[i][j])\n",
    "                    vis[j]=0\n",
    "\n",
    "            return \n",
    "        dfs(0,0)\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        # 预处理 每个学生和导师的兼容性评分\n",
    "        m = len(students)\n",
    "        n = len(students[0])\n",
    "        g = [[0]*m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                for k in range(n):\n",
    "                    g[i][j] += int(students[i][k]==mentors[j][k])\n",
    "\n",
    "        def nextPermutation(arr):\n",
    "            i = len(arr)-2\n",
    "            #双指针\n",
    "            # 找i\n",
    "            while i >= 0 and arr[i] >= arr[i+1]:\n",
    "                i -= 1\n",
    "            if i < 0:\n",
    "                return False\n",
    "            # 找j\n",
    "            else:\n",
    "                j = len(arr)-1\n",
    "                while j >= 0 and arr[i] >= arr[j]:\n",
    "                    j -= 1\n",
    "                # 交换\n",
    "                arr[i],arr[j] = arr[j],arr[i]\n",
    "            # 排序\n",
    "            left = i+1\n",
    "            right = len(arr)-1\n",
    "            while left < right:\n",
    "                arr[left],arr[right] = arr[right],arr[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return True\n",
    "        # 枚举所有的排列组合\n",
    "        ans = 0\n",
    "        p = list(range(m))\n",
    "        while True:\n",
    "            cnt = sum(g[i][p[i]] for i in range(m))\n",
    "            ans = max(ans,cnt)\n",
    "            if not nextPermutation(p):\n",
    "                break\n",
    "        return ans\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, mask):\n",
    "            if i == len(students):\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            for j in range(len(students)):\n",
    "                if mask & (1 << j) == 0:\n",
    "                    cnt = sum([students[i][k] == mentors[j][k] for k in range(len(mentors[j]))])\n",
    "                    res = max(res, cnt + dfs(i+1, mask | (1 << j)) )\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n = len(students)\n",
    "        dct = [[0]*n for _ in range(n)]\n",
    "        m = len(students[0])\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                dct[i][j] = sum(students[i][x]==mentors[j][x] for x in range(m))\n",
    "        \n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x, state):\n",
    "            if x == n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for y in range(n):\n",
    "                if state & (1<<y):\n",
    "                    cur = dct[x][y] + dfs(x+1, state^(1<<y))\n",
    "                    if cur > res:\n",
    "                        res = cur\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, (1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        m, n = len(students), len(students[0])\n",
    "        memo = {}  # 用于保存已经计算过的子问题的结果\n",
    "        \n",
    "        # 计算兼容性评分\n",
    "        def score(student, mentor):\n",
    "            return sum(stu == men for stu, men in zip(student, mentor))\n",
    "        \n",
    "        # 回溯函数，其中 mask 用于记录哪些导师已经被匹配了\n",
    "        def backtrack(i, mask):\n",
    "            if i == m:\n",
    "                return 0\n",
    "            \n",
    "            if (i, mask) in memo:\n",
    "                return memo[(i, mask)]\n",
    "            \n",
    "            max_score = 0\n",
    "            for j in range(m):\n",
    "                if mask & (1 << j) == 0:  # 如果第 j 位是 0，表示第 j 名导师还没有被匹配\n",
    "                    new_mask = mask | (1 << j)  # 更新 mask\n",
    "                    cur_score = score(students[i], mentors[j])  # 计算当前学生和导师的兼容性评分\n",
    "                    next_score = backtrack(i + 1, new_mask)  # 递归求解剩下的学生\n",
    "                    max_score = max(max_score, cur_score + next_score)\n",
    "            \n",
    "            memo[(i, mask)] = max_score\n",
    "            return max_score\n",
    "        \n",
    "        return backtrack(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        store=dict()\n",
    "        store2=dict()\n",
    "        def dp(stu,men,store):\n",
    "            if str([stu,men]) in store2:\n",
    "                return store2[str([stu,men])]\n",
    "            if len(stu)==1:\n",
    "                res=0\n",
    "                if (tuple(stu[0]),tuple(men[0])) in store:\n",
    "                    res+=store[(tuple(stu[0]),tuple(men[0]))]\n",
    "                    return res\n",
    "                else:\n",
    "                    for i in range (len(stu[0])):\n",
    "                        res+=1-abs(stu[0][i]-men[0][i])\n",
    "                    store[(tuple(stu[0]),tuple(men[0]))]=res\n",
    "                    return res\n",
    "            else:\n",
    "                maxx=0\n",
    "                curstu=stu[0]\n",
    "                for ind in range (len(men)):\n",
    "                    curmen=men[ind]\n",
    "                    if (tuple(curstu),tuple(curmen)) in store:\n",
    "                        curres=store[(tuple(curstu),tuple(curmen))]+dp(stu[1:],men[0:ind]+men[ind+1:],store)\n",
    "                    else:\n",
    "                        curres=0\n",
    "                        for i in range (len(curstu)):\n",
    "                            curres+=1-abs(curstu[i]-curmen[i])\n",
    "                        store [(tuple(curstu),tuple(curmen))]=curres\n",
    "                        curres+=dp(stu[1:],men[0:ind]+men[ind+1:],store)\n",
    "                    if curres>maxx:\n",
    "                        maxx=curres\n",
    "                store2[str([stu,men])]=maxx\n",
    "                return maxx\n",
    "        return dp(students,mentors,store)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def track(nums):\n",
    "    if len(nums)==1:\n",
    "        return [[nums[0]]]\n",
    "    result=[]\n",
    "    for i in range(len(nums)):\n",
    "        subresult=track(nums[:i]+nums[i+1:])\n",
    "        for r in subresult:\n",
    "            result.append([nums[i]]+r)\n",
    "    return result\n",
    "tracklist=[]\n",
    "for i in range(8):\n",
    "    nums=[i for i in range(i+1)]\n",
    "    tracklist.append(track(nums))\n",
    "def cost(ls1,ls2):\n",
    "    r=0\n",
    "    for i in range(len(ls1)):\n",
    "        if ls1[i]==ls2[i]:\n",
    "            r+=1\n",
    "    return r\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        n=len(students)\n",
    "        ls=tracklist[n-1]\n",
    "        r=0\n",
    "        for lstrack in ls:\n",
    "            costsum=0\n",
    "            for i in range(n):\n",
    "                costsum+=cost(students[i],mentors[lstrack[i]])\n",
    "            r=max(costsum,r)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n",
    "        def lt1947(students,mentors):\n",
    "            m,n=len(students),len(mentors[0])\n",
    "            score=[[0 for j in range(m)] for i in range(m)]\n",
    "            for i in range(m):\n",
    "                for j in range(m):\n",
    "                    temp=0\n",
    "                    for k in range(n):\n",
    "                        if students[i][k]==mentors[j][k]:temp+=1\n",
    "                    score[i][j]=temp\n",
    "            # print(score)\n",
    "            choices = [str(i) for i in range(m)]\n",
    "            def get_arr(st):\n",
    "                if st==m-1:return [[choice] for choice in choices]\n",
    "                res=[]\n",
    "                for arr in get_arr(st+1):\n",
    "                    for choice in choices:\n",
    "                        if choice not in arr:res.append([choice]+arr)\n",
    "                return res\n",
    "            max_=0\n",
    "            arrs=get_arr(0)\n",
    "            # print(arrs)\n",
    "            for arr in arrs:\n",
    "                temp=0\n",
    "                for i,s in enumerate(arr):\n",
    "                    temp+=score[i][int(s)]\n",
    "                max_=max(max_,temp)\n",
    "            return max_\n",
    "        return lt1947(students,mentors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, ss: List[List[int]], mm: List[List[int]]) -> int:\n",
    "        \n",
    "        q1=[]\n",
    "        q2=[]\n",
    "        n=len(ss)\n",
    "        for x,y in zip(ss,mm):\n",
    "          q=set()\n",
    "          e=set()  \n",
    "          for i in range(len(x)):\n",
    "              q.add((i,x[i]))\n",
    "              e.add((i,y[i]))\n",
    "          q1.append(q)\n",
    "          q2.append(e)\n",
    "        ans=[]\n",
    "        cur=[]\n",
    "        v=Counter()\n",
    "        def g(i):\n",
    "            if i==n:\n",
    "                ans.append(cur.copy())\n",
    "                return \n",
    "            for j in range(n):\n",
    "                if not v[j]:\n",
    "                    v[j]+=1\n",
    "                    cur.append(j)\n",
    "                    g(i+1)\n",
    "                    cur.pop()\n",
    "                    v[j]-=1\n",
    "        g(0)\n",
    "        re=0\n",
    "        for x in ans:\n",
    "            res=0\n",
    "            for i in range(n):\n",
    "               res+=len(q1[i]&q2[x[i]])\n",
    "            re=max(res,re)    \n",
    "        return re            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCompatibilitySum(self, ss: List[List[int]], mm: List[List[int]]) -> int:\n",
    "        q=Counter()\n",
    "        \n",
    "        e=[]\n",
    "        def cd(l1,r1):\n",
    "            cc=0\n",
    "            for x,y in zip(l1,r1):\n",
    "                if x==y:\n",
    "                   cc+=1\n",
    "            return cc        \n",
    "        # for x in ss:\n",
    "        #   cr=Counter()  \n",
    "        #   for i in range(len(x)):\n",
    "        #      cr[(i,x[i])]+=1\n",
    "        #   e.append(cr)      \n",
    "        cur=[]\n",
    "        ans=[]\n",
    "        v=Counter()\n",
    "        def g(i):\n",
    "           if i==n:\n",
    "               ans.append(cur.copy())\n",
    "               return     \n",
    "           for j in range(n):\n",
    "               if v[j]==0:\n",
    "                   v[j]+=1\n",
    "                   cur.append(j)\n",
    "                   g(i+1)\n",
    "                   v[j]-=1\n",
    "                   cur.pop()\n",
    "        n=len(ss)\n",
    "        g(0)\n",
    "        ar=0\n",
    "        for no in ans:    \n",
    "         ce=0\n",
    "         for i in range(n):\n",
    "            l=ss[i]\n",
    "            r=mm[no[i]] \n",
    "            ce+=cd(l,r)\n",
    "         if ar<ce:\n",
    "             ar=ce   \n",
    "        return ar   "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
